package insertsort;

public class Insert {
    /**
     * 时间复杂度 0(n²)
     * 空间复杂度 O(1)
     * 稳定性：稳定/ 稳定的排序可以实现为不稳定的排序，
     *              但是不稳定的排序无法实现为稳定的排序
     * 适用于： 待排序序列 已经基本上趋于有序了
     * @param arr 待排序的数组
     */
    public void sort (int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - 1;
            for (; j >= 0;j --) {
                if (arr[j] > temp) { // 加个等号可以实现为不稳定的排序
                    arr[j+1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j+1] = temp;
        }
    }
}
